package com.yangzhe.algorithm.c036;

// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code07_PreorderInorderBuildBinaryTree_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    // 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
    // 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
    // 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
    // 比如如下两棵树
    //         __2
    //        /
    //       1
    //       和
    //       1__
    //          \
    //           2
    // 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
    // 提交这个类
    public class Codec {


        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder("");
            serializePreOrder(sb, root);

            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.isEmpty()) {
                return null;
            }

            String[] nodes = data.split(",");

            return deserializePreOrder(nodes);
        }

        public void serializePreOrder(StringBuilder sb, TreeNode root) {
            if (root == null) {
                sb.append("#,");
                return;
            }
            // 先序遍历 中左右
            sb.append(root.val).append(",");
            serializePreOrder(sb, root.left);
            serializePreOrder(sb, root.right);
        }

        int cur = 0;

        public TreeNode deserializePreOrder(String[] nodes) {
            String val = nodes[cur++];
            if ("#".equals(val)) {
                return null;
            } else {
                TreeNode node = new TreeNode(Integer.valueOf(val));
                // 构建左树
                node.left = deserializePreOrder(nodes);
                // 左树构建完才会构建右树
                node.right = deserializePreOrder(nodes);

                return node;
            }

        }

    }

}
